BOJ_2591_숫자카드

DP(Dynamic Programming)를 사용해서 가능한 숫자 조합을 만들어 계산하는 문제

입력 + dp 배열 만들기 해서 O(2n)이 걸린다
n은 최대 40이기 때문에 충분히 1초 안으로 들어온다

이 문제의 핵심은 0을 처리하는 것이다
n자리 숫자를 끊어서 1~34까지의 숫자를 만드는 조합 개수를 구하는 것인데 이 카드에는 10, 20도 포함된다

이처럼 끝자리가 0인 카드는 0 단독으로 구성할 수 없기 때문에 따로 처리해줘야 한다

로직

1. 직전 숫자 + 현재 숫자로 34이하로 만들 수 있다면 dp[i] = dp[i-1] + dp[i-2] 이다. 'dp[i-1] + 한 자리 숫자'와 'dp[i-2] + 이전 숫자를 더한 두 자리 숫자'로 생각하면 된다
2. 직전 숫자 + 현재 숫자로 34가 초과된다면 dp[i] = dp[i-1] 이다. 'dp[i-1] + 한 자리 숫자' 인 경우만 더하는 것이다.

이렇게 큰 구성에서 0의 경우를 따로 처리한다
nums[i-1], nums[i], nums[i+1] 이 0이라면 모두 dp[i] = dp[i-1]이 된다

1. i - 1이 0인 경우는 'dp[i-1] + 새로 시작하는 한 자리 숫자'이다
2. i가 0인 경우는 'dp[i-1] + 직전 숫자에 붙어야 하는 0'이다
3. i+1이 0인 경우는 'dp[i-1] + 끝에 0을 붙일 숫자'이다

package BJO;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BJO_2591_숫자카드 {
    // 숫자는 1~34
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String num = br.readLine();

        int[] nums = new int[num.length() + 1];
        int[] dp = new int[num.length() + 1];

        for (int i = 1; i < nums.length; i++) {
            nums[i] = num.charAt(i - 1) - '0';
        }

        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i < nums.length; i++) {
            int n = nums[i - 1] * 10 + nums[i];
            if (nums[i] == 0 || nums[i - 1] == 0 || i + 1 < nums.length && (nums[i + 1] == 0) || n > 34) {
                dp[i] = dp[i - 1];
            } else {
                dp[i] = dp[i - 1] + dp[i - 2];
            }
        }

        System.out.println(dp[num.length()]);
    }
}